<html>
<head>
  <title>链表</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="1091"/>
<h1>链表</h1>

<div>
<span><div><div><font style="font-size: 24pt; color: rgb(28, 51, 135);"><b>数据结构-链表(Linked List)</b></font></div><div><br/></div><div><font style="font-size: 14pt;"><b>python实现</b></font></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class ListNode:</div><div>    def __init__(self, val):</div><div>        self.val = val</div><div>        self.next = None</div><div><br/></div><div><br/></div><div>############################</div><div><span style="font-weight: bold; font-family: Monaco; font-size: 9pt;">反转链表   </span><span style="font-family: Monaco; font-size: 9pt; line-height: 1.45;">单向链表</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-weight: bold; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">链表的基本形式是：</span><span style="-en-paragraph: true; font-weight: bold; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">1 -&gt; 2 -&gt; 3 -&gt; null</span><span style="-en-paragraph: true; font-weight: bold; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">，反转需要变为</span> <span style="-en-paragraph: true; font-weight: bold; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">3 -&gt; 2 -&gt; 1 -&gt; null</span><span style="-en-paragraph: true; font-weight: bold; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">。这里要注意：</span></div><ul><li>访问某个节点 curt.next 时，要检验 curt 是否为 null。</li><li>要把反转后的最后一个节点（即反转前的第一个节点）指向 null。</li></ul><div>#############################</div><div><span>    </span></div><div><span><span>    </span><font style="color: rgb(227, 0, 0);">def reverse(self, head):</font></span></div><div><span><font style="color: rgb(227, 0, 0);"><span>    <span>    prev = None</span></span><br/></font></span></div><div><span><font style="color: rgb(227, 0, 0);"><span><span>    <span>    while head:</span></span><br/></span></font></span></div><div><span><font style="color: rgb(227, 0, 0);"><span><span>    <span>    <span>    temp = head.next</span></span></span><br/></span></font></span></div><div><span><font style="color: rgb(227, 0, 0);"><span><span>    <span>    <span>    head.next = prev</span></span></span><br/></span></font></span></div><div><span><font style="color: rgb(227, 0, 0);"><span><span>    <span>    <span>    prev = head</span></span></span><br/></span></font></span></div><div><span><font style="color: rgb(227, 0, 0);"><span><span>    <span>    <span>    head = temp</span></span></span><br/></span></font></span></div><div><span><font style="color: rgb(227, 0, 0);"><span><span>    <span>    return prev</span></span><br/></span></font></span></div><h3>###############################</h3><h4><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">双向链表</span></h4><div><span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">和单向链表的区别在于：双向链表的反转核心在于</span><span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">next</span><span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">和</span><span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">prev</span><span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">域的交换，还需要注意的是当前节点和上一个节点的递推。</span></div><div>########################################</div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">class DListNode:</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    </span>def __init__(self, val):</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    </span></span>self.val = val</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    </span></span>self.prev = self.next = null</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    </span>def reverse(self, head):</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    </span></span>curt = None</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    </span></span>while head:</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    <span>    </span></span></span>curt = head</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    <span>    </span></span></span>head = curt.next</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    <span>    </span></span></span>curt.next = curt.prev</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    <span>    </span></span></span>curt.prev = head</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"><span>    <span>    </span></span>return curt</span></div><div><br/></div><div>########################################</div><div><span style="font-family: Monaco;"><font style="font-size: 16pt; color: rgb(28, 51, 135);"><b>删除链表中的某个节点</b></font></span></div><div><span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">一定需要知道这个点的前继节点，所以需要一直有指针指向前继节点。还有一种删除是伪删除，是指复制一个和要删除节点值一样的节点，然后删除，这样就不必知道其真正的前继节点了。</span></div><div><span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">然后只需要把</span> <span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">prev -&gt; next = prev -&gt; next -&gt; next</span> <span style="-en-paragraph: true; font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">即可。但是由于链表表头可能在这个过程中产生变化，导致我们需要一些特别的技巧去处理这种情况。就是下面提到的 Dummy Node。</span></div><div>##########################################</div><div><br/></div><div><br/></div><h2><span style="font-family: Monaco;"><font style="font-size: 16pt; color: rgb(28, 51, 135);">链表指针的鲁棒性</font></span></h2><div>###############################################</div><div><br/></div><div><br/></div></div><div><br/></div><div><font style="font-size: 16pt; color: rgb(28, 51, 135);"><b>Dummy Node</b></font></div><div>“哑节点”和“假人头节点”</div><div><span>    </span>Dummy node 是一个虚拟节点，也可以认为是标杆节点。Dummy node 就是在链表表头 head 前加一个节点指向 head，即 dummy -&gt; head。Dummy node 的使用多针对单链表没有前向指针的问题，保证链表的 head 不会在删除操作中丢失。除此之外，还有一种用法比较少见，就是使用 dummy node 来进行head的删除操作，比如 Remove Duplicates From Sorted List II，一般的方法current = current.next 是无法删除 head 元素的，所以这个时候如果有一个dummy node在head的前面。</div><div><span>    </span>所以，当链表的 head 有可能变化（被修改或者被删除）时，使用 dummy node 可以很好的简化代码，最终返回 dummy.next 即新的链表</div><div><br/></div><h2><font style="font-size: 16pt; color: rgb(28, 51, 135);">快慢指针</font></h2><div><span style="-en-paragraph: true;"><span>    </span>快慢指针也是一个可以用于很多问题的技巧。所谓快慢指针中的快慢指的是指针向前移动的步长，每次移动的步长较大即为快，步长较小即为慢，常用的快慢指针一般是在单链表中让快指针每次向前移动2，慢指针则每次向前移动1。快慢两个指针都从链表头开始遍历，于是快指针到达链表末尾的时候慢指针刚好到达中间位置，于是可以得到中间元素的值。快慢指针在链表相关问题中主要有两个应用：</span></div><div><br/></div><ul><li>快速找出未知长度单链表的中间节点 设置两个指针 *fast、*slow 都指向单链表的头节点，其中*fast的移动速度是*slow的2倍，当*fast指向末尾节点的时候，slow正好就在中间了。</li><li>判断单链表是否有环 利用快慢指针的原理，同样设置两个指针 *fast、*slow 都指向单链表的头节点，其中 *fast的移动速度是*slow的2倍。如果 *fast = NULL，说明该单链表 以 NULL结尾，不是循环链表；如果 *fast = *slow，则快指针追上慢指针，说明该链表是循环链表。</li></ul><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></div></span>
</div></body></html> 